#include<stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>

#include <string>

using namespace std;

// 串的顺序存储

#define MAXSIZE 10
typedef int ElemType;  // 定义元素类型

typedef struct{
    char ch[MAXSIZE];
    int length;
}SString;

// 赋值
bool StrAssign(SString &T, string chars){
    if (chars.length() > MAXSIZE) return false;
    for (int i = 1; i < chars.length(); i++)
    {
        T.ch[i] = chars[i];
        T.length ++;
    }
    return true;
}

// 求串长
int StrLength(SString S){
    return S.length;
}

// 求子串
bool SubString(SString &Sub, SString S, int pos, int len){
    // 子串范围越界
    if (pos + len -1 > S.length) return false;
    for(int i=pos; i<pos+len; i++){
        Sub.ch[i-pos+1]=S.ch[i];
    }
    Sub.length = len;
    return true;
}

// 比较
int StrCompare(SString S, SString T){
    for(int i=1; i<=S.length && i<=T.length; i++){
        if(S.ch[i]!=T.ch[i]) return S.ch[i] - T.ch[i];
    }
    return S.length-T.length;
}

// 定位操作
int Index(SString S, SString T){
    int i=1, n=StrLength(S), m=StrLength(T);
    SString sub;
    while (i<=n-m+1)
    {
        SubString(sub, S, i, m);
        if (StrCompare(sub, T)!=0) ++i;
        else return i;
    }
    return 0;
}

// 朴素模式匹配算法
int Index_t(SString S, SString T){
    int k=1;
    int i=k, j=1;
    while (i<=S.length && j<=T.length){
        printf("%c,%d<==>%c,%d\n", S.ch[i], i, T.ch[j], j);
        if(S.ch[i]==T.ch[j]){
            ++i;
            ++j;
        }else{
            k++;
            i=k;
            j=1;
        }
    }
    if (j>T.length) 
        return k;
    else 
        return 0;
}

// KMP算法
int Index_KMP(SString S, SString T, int next[]){
    int i=1,j=1;
    while (i<=S.length&&j<=T.length)
    {
        if (j==0||S.ch[i]==T.ch[j])
        {
            ++i;
            ++j;
        }
        else j=next[j];
    }
    if (j>T.length) i-T.length;
    else 0;
}


int main(){
    SString T;
    SString S;
    StrAssign(S, "abcdefg");
    StrAssign(T, "de");
    printf("%d\n", Index_t(S, T));
    // printf("%d\n", sizeof(ch)/sizeof(ch[0]));
    system("pause");
    return 0;
}
